Search for: All records

A fundamental problem in circuit complexity is to find explicit functions that require large depth to compute. When considering the natural DeMorgan basis of {OR,AND}, where negations incur no cost, the best known depth lower bounds for an explicit function in NP have the form (3-o(1))log₂ n, established by Håstad (building on others) in the early 1990s. We make progress on the problem of improving this factor of 3, in two different ways: - We consider an "algorithmic method" approach to proving stronger depth lower bounds for non-uniform circuits in the DeMorgan basis. We show that slightly faster algorithms (than what is known) for counting the number of satisfying assignments on subcubic-size DeMorgan formulas would imply supercubic-size DeMorgan formula lower bounds, implying that the depth must be at least (3+ε)log₂ n for some ε > 0. For example, if #SAT on formulas of size n^{2+2ε} can be solved in 2^{n - n^{1-ε}log^k n} time for some ε > 0 and a sufficiently large constant k, then there is a function computable in 2^{O(n)} time with a SAT oracle which does not have n^{3+ε}-size formulas. In fact, the #SAT algorithm only has to work on formulas that are a conjunction of n^{1-ε} subformulas, each of which is n^{1+3ε} size, in order to obtain the supercubic lower bound. As a proof of concept, we show that our new algorithms-to-lower-bounds connection can be applied to prove new lower bounds for "hybrid" DeMorgan formula models which compute interesting functions at their leaves. - Turning to the {NAND} basis, we establish a greater-than-(3 log₂ n) depth lower bound against uniform circuits solving the SAT problem, using an extension of the "indirect diagonalization" method for NAND formulas. Note that circuits over the NAND basis are a special case of circuits over the DeMorgan basis; however, hard functions such as Andreev’s function (known to require depth (3-o(1))log₂ n in the DeMorgan basis) can still be computed with NAND circuits of depth (3+o(1))log₂ n. Our results imply that SAT requires polylogtime-uniform NAND circuits of depth at least 3.603 log₂ n. 

Cracked and deteriorated asphalt are common problems on our roads, leading to safety concerns and requiring significant resources for rehabilitation and reconstruction. This study investigates bio-fog seals, a promising eco-friendly solution utilizing bio-based rejuvenators. These treatments penetrate aged asphalt, restoring its flexibility and resistance to cracking. We assessed the effectiveness of two bio-fog seal formulations—one containing sub-epoxidized soybean oil (SESO) and the other combining SESO with a biopolymer (BioMag). Applied to real pavement sections, the research evaluated how these bio-seals impacted key performance factors, such as stiffness, permeability, and drying time, and safety factors, including skid resistance and pavement marking visibility. The results indicate the bio-seals did not compromise skid resistance and the reflectivity of the markings, eliminating the need for repainting stripes. Additionally, they successfully reduced pavement stiffness, making the asphalt more flexible and crack-resistant. Remarkably, with rapid setting times, under 30 min, these treatments minimize traffic disruption and do not require a blotter material. Overall, this research demonstrates the potential of bio-fog seals as a sustainable solution for extending pavement lifespan and lowering long-term maintenance costs. 

Given the need for ever higher performance, and the failure of CPUs to keep providing single-threaded performance gains, engineers are increasingly turning to highly-parallel custom VLSI chips to implement expensive computations. In VLSI design, the gates and wires of a logical circuit are placed on a 2-dimensional chip with a small number of layers. Traditional VLSI models use gate delay to measure the time complexity of the chip, ignoring the lengths of wires. However, as technology has advanced, wire delay is no longer negligible; it has become an important measure in the design of VLSI chips [Markov, Nature (2014)]. Motivated by this situation, we define and study a model for VLSI chips, called wire-delay VLSI, which takes wire delay into account, going beyond an earlier model of Chazelle and Monier [JACM 1985]. - We prove nearly tight upper bounds and lower bounds (up to logarithmic factors) on the time delay of this chip model for several basic problems. For example, And, Or and Parity require Θ(n^{1/3}) delay, while Addition and Multiplication require ̃ Θ(n^{1/2}) delay, and Triangle Detection on (dense) n-node graphs requires ̃ Θ(n) delay. Interestingly, when we allow input bits to be read twice, the delay for Addition can be improved to Θ(n^{1/3}). - We also show that proving significantly higher lower bounds in our wire-delay VLSI model would imply breakthrough results in circuit lower bounds. Motivated by this barrier, we also study conditional lower bounds on the delay of chips based on the Orthogonal Vectors Hypothesis from fine-grained complexity. 

ABSTRACT We present a search for luminous long-duration ambiguous nuclear transients (ANTs) similar to the unprecedented discovery of the extreme ambiguous event AT2021lwx with a $$\gt 150$$ d rise time and luminosity $$10^{45.7}$$ erg s$$^{-1}$$. We use the Lasair transient broker to search Zwicky Transient Facility (ZTF) data for transients lasting more than one year and exhibiting smooth declines. Our search returns 59 events, 7 of which we classify as ANTs assumed to be driven by accretion onto supermassive black holes. We propose the remaining 52 are stochastic variability from regular supermassive black hole accretion rather than distinct transients. We supplement the seven ANTs with three nuclear transients in ZTF that fail the light curve selection but have clear single flares and spectra that do not resemble typical active galactic nucleus. All of these 11 ANTs have a mid-infrared flare from an assumed dust echo, implying the ubiquity of dust around the black holes giving rise to ANTs. No events are more luminous than AT2021lwx, but one (ZTF19aamrjar) has twice the duration and a higher integrated energy release. On the other extreme, ZTF20abodaps reaches a luminosity close to AT2021lwx with a rise time $$\lt 20$$ d and that fades smoothly in $$\gt 600$$ d. We define a portion of rise-time versus flare amplitude space that selects ANTs with $$\sim 50$$ per cent purity against variable AGNs. We calculate a volumetric rate of $$\gtrsim 3\times 10^{-11}$$ Mpc$$^{-1}$$ yr$$^{-1}$$, consistent with the events being caused by tidal disruptions of intermediate and high-mass stars.